package 优先级队列;

import javafx.util.Pair;

import java.util.*;

public class 前k个高频单词 {
//    public List<Character> findMaxKth(char[] arr, int k)
//    {
//        int len = arr.length;
//        HashMap<Character,Integer> hashMap = new LinkedHashMap<>();
//        HashMap<Integer,Character> reverseMap = new LinkedHashMap<>();
//        for( char z : arr)
//        {
//            if(hashMap.containsKey(z))
//            {
//                int count = hashMap.get(z);
//                hashMap.put(z,count+1);
//                reverseMap.put(count+1,z);
//            }
//            else{
//                hashMap.put(z,1);
//                reverseMap.put(1,z);
//            }
//        }
//
//        PriorityQueue<Integer> q = new PriorityQueue<>();
//       for(int i = 0 ; i< len ; i++)
//       {
//           if(q.size()> k)
//           {
//               q.poll();
//           }
//           else{
//               q.offer(hashMap.get(arr[i]));
//           }
//       }
//        List<Character> list = new ArrayList<>();
//       while(!q.isEmpty())
//       {
//           int temp = q.poll();
//           list.add(reverseMap.get(temp));
//
//       }
//       return list;
//
//
//    }
    public List<String> topKFrequent(String [] arr ,int k)
    {
        HashMap<String,Integer> hashMap = new HashMap<>();
        for(String s : arr)
        {
            hashMap.put(s,hashMap.getOrDefault(s,0)+1);
        }
        // 创建堆
        PriorityQueue<Pair<String,Integer>> heap = new PriorityQueue<>(
                (a,b)->
                {
                    if(a.getValue().equals(b.getValue()))// 频次相同时,字典序按大根堆排列
                    {
                        return b.getKey().compareTo(a.getKey());
                    }
                    return a.getValue()-b.getValue();
                }
                );
        // 3. TopK 主逻辑
        for(Map.Entry<String,Integer> e : hashMap.entrySet())
        {
            heap.offer(new Pair<>(e.getKey(),e.getValue()));
            if(heap.size()>k)
            {
                heap.poll();
            }
        }
        // 4.提取结果
        List<String> ret  = new ArrayList<>();
        while (!heap.isEmpty())
        {
            ret.add(heap.poll().getKey());
        }
        //逆序数组
        Collections.reverse(ret);
        return ret;


    }
}
